/**
 * @author: yangwk
 * @date: 2023/7/28
 * @description:
 **/
public class 最长回文子串 {
    public static void main(String[] args) {
        System.out.println(longest("abcdcbeh"));
        System.out.println(dynamicLongest("abcdcbeh"));
    }

    public static String longest(String str) {
        int length = str.length();
        String maxStr = "";
        int maxLength = 0;
        //以i为结尾
        for (int i = 0; i < length; i++) {
            //从j开头
            for (int j = 0; j < i; j++) {
                //截取就j,i的字符串
                if (is(str.substring(j, i + 1))) {
                    if (i + 1 - j > maxLength) {
                        maxLength = i + 1 - j;
                        maxStr = str.substring(j, i + 1);
                    }
                }
            }
        }
        return maxLength == 0 ? "无回文" : maxStr;
    }

    public static String dynamicLongest(String str) {
        int length = str.length();
        String maxStr = "";
        int maxLength = 0;
        boolean[][] visited = new boolean[length][length];
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < i; j++) {
                boolean is = visited[j + 1][i - 1] || j - i <= 1;
                if (is && str.charAt(i) == str.charAt(j)) {
                    if (i + 1 - j > maxLength) {
                        maxLength = i + 1 - j;
                        maxStr = str.substring(j, i + 1);
                    }
                    visited[j][i] = true;
                }
            }
        }
        return maxLength <= 1 ? "无回文" : maxStr;
    }

    public static boolean is(String str) {
        int length = str.length();
        //判断回文
        for (int i = 0, j = length - 1; i < j; i++, j--) {
            if (str.charAt(i) != str.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}
